import java.util.Arrays;

/**
 * @Description:环绕字符串中唯一的子字符串
 * 把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，
 * 所以 s 看起来是这样的：
 * "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." . 
 * 现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。
 *
 * 输入: p = "zab"
 * 输出: 6
 * 解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。
 *
 * @Date:Create in 20:24  2022/5/25
 */
public class findSubstringInWraproundString0467 {
    public static void main(String[] args) {
        String p = "zab";
        int a = findSubstringInWraproundString1(p);
        System.out.println(a);
    }

    //动态规划
    public static int findSubstringInWraproundString1(String p) {
        int[] dp = new int[26];
        int k = 0;
        for (int i = 0; i < p.length(); i++) {
            if(i > 0 &&(p.charAt(i) - p.charAt(i-1) + 26) % 26 == 1){//字符之差为1或-25
                ++k;
            }else{
                k = 1;
            }
            dp[p.charAt(i) - 'a'] = Math.max(dp[p.charAt(i) - 'a'],k);

        }
        //将数组dp中的所有数进行累加求和
        return Arrays.stream(dp).sum();
    }
}
